package Alibaba;

/**
 * @author zhangmin
 * @create 2022-01-30 12:00
 *
 * 400. 第 N 位数字
 * 给你一个整数 n ，请你在无限的整数序列 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...] 中找出并返回第 n 位上的数字。
 * 思路：要找第n位数字，需要找到第n位数字在第几个整数的第几位上
 * digit位数的最小整数位10^(digit-1)，最大数为：10^digit-1;
 * 一共有9*10^（digit-1）个,所有digit位数的位数一共digit*9*10^(digit-1).
 */
public class findNthDigit400 {
    public int findNthDigit(int n) {
        //digit记录当前为位数，count表示当前位数的整数有多少个，两者相乘得到当前位数的整数的所有位数之和
        //1、求出第n位所在的整数的位数
        int digit=1,count=9;
        while (n>(long)digit*count){
            n-=digit*count;
            digit++;
            count*=10;
        }
        //2、求出第n为在第几个整数中
        int index=n-1;
        int start= (int) Math.pow(10,digit-1);
        int num=start+index/digit;
        //3、求出第n为在num中的第几位上
        int digitIndex=index%digit;
        //4、返回num上的第digitIndex位的数字，先去掉后面的digit-digitIndex-1位，然后在模10取余得到
        return  (num/(int)(Math.pow(10,digit-digitIndex-1)))%10;
    }
}
